package com.chaos.eurekaproducer.leetCode;

import com.chaos.eurekaproducer.basic.TreeNode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @author liaopeng
 * @title: Offer07
 * @projectName eureka-producer
 * @description:
 * 输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字
 * 前序遍历 preorder = [3,9,20,15,7]
 * 中序遍历 inorder = [9,3,15,20,7]
 *
 *
 * 思路：
 * 1、根据前序遍历首个元素即为根节点，找到根节点。
 * 2、根据根节点，将中序遍历分为：左子树---根节点---右子树
 * 3、根据中序遍历左子树个数，将前序遍历分为：跟节点---左子树---右子树
 *
 *
 * 前序遍历：根节点索引为root，那么左子树根节点索引为root+1，如果知道左子树大小size，那么就知道右子树根节点索引为root+size+1
 * @date 2021/6/8上午10:11
 */
public class Offer07 {
    static Map<Integer,Integer> dic = new HashMap<>();
    public static TreeNode buildTreeNode(int[] preorder, int[] inorder){
        if (preorder.length==1){
            return new TreeNode(preorder[0]);
        }
        for (int i = 0; i < preorder.length; i++) {
            dic.put(inorder[i],i);
        }
        return myBuild(preorder,0,0,inorder.length-1);
    }

    /**
     *
     * @param preorder：前序遍历数组
     * @param root:根节点在前序遍历的索引
     * @param left：中序遍历左边界
     * @param right：中序遍历右边界
     * @return
     */
    public static TreeNode myBuild(int[] preorder,int root,int left,int right){
        if (left>right){return null;}
        TreeNode rootNode = new TreeNode(preorder[root]);
        int i = dic.get(preorder[root]);//根节点中序遍历索引
        rootNode.setLeft(myBuild(preorder,root+1,left,i-1));
        rootNode.setRight(myBuild(preorder,root+i-left+1,i+1,right));//root+i-left+1为根节点索引+左子树大小+1
        return rootNode;
    }

    public static void main(String[] args) {
        int[] preorder = new int[]{3,9,20,15,7};
        int[] inorder = new int[]{9,3,15,20,7};
        TreeNode treeNode = buildTreeNode(preorder, inorder);
        System.out.println(treeNode);
    }
}
